package 数组.排序数组中查找数字I;

/**
 * @author: wh(1835734390 @ qq.com)
 * @date: 2023/3/3 17:24
 * @description: 剑指offer
 * @version:
 */
public class Solution {
    public static void main(String[] args) {
        int[] array = {1};
        System.out.println(search2(array,1));
    }

    //基本解法
    public static int search(int[] nums, int target) {
        int ans = 0;
        for (Integer num: nums) {
            if (num == target){
                ans++;
            }
        }
        return ans;
    }

    //二分查找
    public static int search2(int[] nums, int target) {
        int ans = 0;
        int left = 0;
        int right = nums.length - 1;
        while (left <= right){
          int mid = left + (right - left)/2;
          if (nums[mid] == target){
              ans++;
              int index = mid + 1;
              while (index <= right && nums[index] == target){
                  ans++;
                  index++;
              }
              index = mid - 1;
              while (index >= left && nums[index] == target){
                  ans++;
                  index--;
              }
              //这里记得要break
              break;
          }else if (nums[mid] > target){
              right = mid - 1;
          }else if (nums[mid] < target){
              left = mid + 1;
          }
        }
        return ans;
    }
}
